package com.jinan.algorithm.Backtrace;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 有n个城市，其中一些彼此相连，另一些没有相连。如果城市a与城市b直接相连，且城市b与城市c直接相连，那么城市a与城市c间接相连。
 * 省份是一组直接或间接相连的城市,组内不含其他没有相连的城市。给你一个n*n的矩阵isConnected，
 * 其中isConnected[i][i]=1表示第i个城市和第j个城市直接相连,而isConnected[i][j]=0表二者不直接相连。
 * 返回矩阵中省份的数量。
 */
public class ProvinceCount {
    private int[][] isConnected;
    private boolean[] visited;
    public static void main(String[] args) {
        ProvinceCount pc = new ProvinceCount();
        int[][] isConnected = {{1,1,0},{1,1,0},{0,0,1}};
        System.out.println(pc.findCircleNum(isConnected));
        System.out.println(pc.findCircleNum2(isConnected));
        System.out.println(pc.findCircleNum3(isConnected));
    }
//    深度优先
    public int findCircleNum(int[][] M) {
        int n = M.length;
        isConnected=M;
        visited=new boolean[n+1];
        int province=0;
        for (int i=0;i<n;i++){
            if (!visited[i]){
                visited[i]=true;
                dfs(i);
                province++;
            }
        }
        return province;
    }

    private void dfs(int city) {
        for (int i=0;i<isConnected.length;i++){
            if (isConnected[city][i]==1 && !visited[i]){
                visited[i]=true;
                dfs(i);
            }
        }
    }

//    广度优先
    public int findCircleNum2(int[][] M) {
        int n = M.length;
        isConnected=M;
        visited=new boolean[n+1];
        int province=0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i=0;i<n;i++){
            if(!visited[i]){
                bfs(queue, i, n);
                province++;
            }
        }
        return province;
    }

    private void bfs(Queue<Integer> queue, int i, int n) {
        queue.offer(i);
        while (!queue.isEmpty()){
            int j= queue.poll();
            for (int k = 0; k< n; k++){
                if (isConnected[j][k]==1 && !visited[k]){
                    queue.offer(k);
                    visited[k]=true;
                }
            }
        }
    }
//    并查集
    public int findCircleNum3(int[][] M) {
        int n = M.length;
        isConnected=M;
        int province=0;
        int[] head=new int[n+1];
        int[] level=new int[n+1];
        for (int i=0;i<n;i++){
            head[i]=i;
            level[i]=1;
        }
        for (int i=0;i<n;i++){
            for (int j=i+1;j<n;j++){
                if (isConnected[i][j]==1){
                    union(head, level, i, j);
                }
            }
        }
        for (int i=0;i<n;i++){
            if (head[i]==i){
                province++;
            }
        }
        return province;
    }

    private void union(int[] head, int[] level, int i, int j) {
        int iHead=findHead(head, i);
        int jHead=findHead(head, j);
        if (iHead==jHead){
            return;
        }
        if (level[iHead]>level[jHead]){
            head[jHead]=iHead;
        }else if (level[iHead]<level[jHead]){
            head[iHead]=jHead;
        }else if (level[iHead]==level[jHead]){
            head[jHead]=iHead;
            level[jHead]++;
            level[iHead]++;
        }
    }

    private int findHead(int[] head, int i) {
        int j=i;
        while(head[j]!=j){
            j=head[j];
        }
        head[i]=j;
        return j;
    }
}
